#include <stdio.h>
void InsertSort(int* a,int n){
  for(int i = 0; i < n - 1; i++){
    int end = i;
    int x = a[end + 1];
    while(end >= 0){
      if(a[end] > x){
        a[end+1] = a[end];
        end--;
      }
      else{
        break;
      }
    }
    a[end+1] = x;
  }
}
void ShellSort(int* a,int n){
  int gap = 5;
  while(gap > 1){
    gap /= 2;
    for(int i = 0;i < n - gap; i++){
      int end = i;
      int x = a[end + gap];
      while(end >= 0){
        if(a[end] > x){
          a[end + gap] = a[end];
          end -= gap;
        }
        else{
          break;
        }
      }
      a[end + gap] = x;
    }
  }
}
void swap(int* x,int* y){
  int tmp = *x;
  *x = *y;
  *y = tmp;
}
void BubbleSort(int* a,int n ){
  int SortBorder = n - 1;
  int LastChangeIndex = 0;
  for(int i = 0; i < n - 1; i++){
    int flag = 0;
    for(int j = 0; j < SortBorder; j++){
      if(a[j] > a[j+1]){
        swap(&a[j], &a[j+1]);
        flag = 1;
        LastChangeIndex = j;
      }
    }
    SortBorder = LastChangeIndex;
    if(flag == 0){
      break;
    }
  }
}
int GetMidIndex(int* a, int left ,int right){
  int mid = (left + right) / 2;
  if(a[mid] > a[left]){
    if(a[right] > a[mid]){
      return mid;
    }
    else if(a[left] > a[right]){
      return left;
    }
    else{
      return right;
    }
  }
  else{//a[mid] < a[left]
    if(a[right] < a[mid]){
      return mid;
    }
    else if(a[left] < a[right]){
      return left;
    }
    else{
      return right;
    }
  }
}
int HoareVersion(int* a,int left,int right){
  int mid = GetMidIndex(a, left, right);
  swap(&a[left], &a[mid]);

  int keyi = left;
  while(left < right){
    //右边先走，找小
    while(left < right && a[right] >= a[keyi]){
      right--;
    }
    //左边再走，找大
    while(left < right && a[left] <= a[keyi]){
      left++;
    }
    swap(&a[left], &a[right]);
  }
  swap(&a[left], &a[keyi]);
  return left;
}
int HoleVersion(int* a, int left, int right){
  int mid = GetMidIndex(a, left, right);
  swap(&a[mid],&a[left]);
  int key = left;
  int hole = left;
  while(left < right){
    //右边找小，放入左边坑位，在将坑位移至右边
    while(left < right && a[right] >= key){
      right--;
    }
    a[hole] = a[right];
    hole = right;
    //左边找大，放入右边坑位，再将坑位移至左边
    while(left < right && a[left] <= key){
      left++;
    }
    a[hole] = a[left];
    hole = left;
  }
  a[hole] = key;
  return hole;
}
int IndexVersion(int* a,int left, int right){
  int mid = GetMidIndex(a, left, right);
  swap(&a[mid],&a[left]);
  int key = left;
  int cur = left, prev = left;
  while(cur <= right){
    if(a[cur] < a[key] && prev++ != cur){
      swap(&a[cur], &a[prev]);
    }
    cur++;
  }
  swap(&a[prev],&a[key]);
  return prev;
}
void QucikSort(int* a, int left, int right){
  if(left >= right){
    return;
  }
  if(right - left + 1< 10){
    InsertSort(a + left, right - left + 1);
  }
  else{
    int keyi = IndexVersion(a, left, right);
    //[left,keyi - 1] keyi [keyi + 1, right]
    QucikSort(a, left, keyi - 1);
    QucikSort(a, keyi + 1, right);
  }
}
void SelectSort(int* a,int n){
  int begin = 0, end = n - 1;
  while(begin < end){
    int mini = begin, maxi = begin;
    for(int i = begin; i <= end; i++){
      if(a[i] < a[mini])
        mini = i;
      if(a[i] > a[maxi])
        maxi = i;
    }
    swap(&a[begin],&a[mini]);
    if(maxi == begin)
      maxi = mini;
    swap(&a[end],&a[maxi]);
    begin++;
    end--;
  }
}
void adjustUp(int* a,int kid){
  int parent = (kid - 1) / 2;
  while(kid){
    if(a[kid] > a[parent]){
      swap(&a[kid],&a[parent]);
      kid = parent;
      parent = (kid - 1) / 2;
    }
    else{
      break;
    }
  }
}
void adjustDown(int* a,int size,int parent){
  int kid = parent * 2 + 1;
  while(kid < size){
    if(kid + 1 < size && a[kid+1] > a[kid] )
      kid++;
    if(a[kid] > a[parent]){
      swap(&a[kid],&a[parent]);
      parent = kid;
      kid = parent*2+1;
    }
    else{
      break;
    }
  }
}
void HeapSort(int* a,int n){
  //建堆
 // for(int i = 1; i < n; i++){
 //   adjustUp(a,i);
 // }
  for(int i = (n-1-1)/2; i>=0; i--){
    adjustDown(a,n,i);
  }
  //排序
  for(int j = n-1; j>0; j--){
    swap(&a[0],&a[j]);
    adjustDown(a,n,j);
  }
}
int main(){
  int a[] = {1,2,9,8,7,3,4,6,5};
  int n = sizeof(a)/sizeof(a[0]);
  for(int i = 0; i < n; i++){
    printf("%d ",a[i]);
  }
  printf("\n");
  //InsertSort(a,n);
  //ShellSort(a,n);
  //BubbleSort(a,n);
  //QucikSort(a, 0, n - 1);
  SelectSort(a, n);
  for(int i = 0; i < n; i++){
    printf("%d ",a[i]);
  }
  printf("\n");
  return 0;
}
